package _11_整理题目._7_查找排序._1_排序算法;

import org.junit.Test;
import util.UtilTool;

import java.util.Arrays;

/**
 * 思路：（以增序为例）
 * 每次比较相邻的两个数，如果第一个大于第二个，则交换；
 * 这样遍历一次后可以将最大的数值放到最后，即确定了最后一个位子的值；
 * 继续重头开始，可以依次确认倒数第二个，第三个位子的值...，共需要 n-1 轮
 * 时间复杂度：最坏 o(n2)，如果是有序的，也要遍历比较 o(n)
 * 
 * 代码分析：
 *      第一层循环控制轮次 n-1 次（n是数组的元素个数）
 *      第二层循环，i 表示数组下标位置，每次交换时，第一轮不需要遍历最后一个，所以 i < n-1-k
 */
public class _01_冒泡排序 {
    
    public void bubbleSort(int[] array) {
        int n = array.length;
        for (int k = 0; k <= n-2; k++) {
            for (int i = 0; i <= n-2-k; i++) { // 当k=0时，i是数组的下标，最大取 n-2
                if (array[i] > array[i+1]) {
                    int temp = array[i];
                    array[i] = array[i+1];
                    array[i+1] = temp;
                }
            }
        }
    }
    
    @Test
    public void main() {
//        int[] input = {1,4,6,2,5,3,8};
//        System.out.println(Arrays.toString(input));
//        bubbleSort(input);
//        System.out.println(Arrays.toString(input));
        int[] input1 = UtilTool.getRandomArray(10, 0, 100);
        int[] input2 = Arrays.copyOf(input1, input1.length);
        System.out.println(Arrays.toString(input1));
        System.out.println(Arrays.toString(input2));
        bubbleSort(input1);
        System.out.println(Arrays.toString(input1));
        Arrays.sort(input2);
        System.out.println(Arrays.toString(input2));
    }
}
